import collections


class Solution(object):
    def addOperators(self, num, target):
        """
        :type num: str
        :type target: int
        :rtype: List[str]
        """
        n = len(num)
        out = []

        def judge(s):
            left_index = 0
            right_index = 0
            stack = collections.deque()
            last = '+'
            m = len(s)
            while right_index < m:
                if s[right_index] in {'+', '-', '*'}:
                    if right_index > left_index:
                        now = int(s[left_index: right_index])
                        if last == '*':
                            stack[-1] = stack[-1] * now
                        if last == '+':
                            stack.append(now)
                        if last == '-':
                            stack.append(-now)
                        last = s[right_index]
                    left_index = right_index + 1
                right_index += 1
            if right_index > left_index:
                now = int(s[left_index: right_index])
                if last == '*':
                    stack[-1] = stack[-1] * now
                if last == '+':
                    stack.append(now)
                if last == '-':
                    stack.append(-now)
            result = sum(stack)
            if result == target:
                out.append(s)

        def search(s, i):
            s += num[i]
            if i < n - 1:
                if s[-1] == '0':
                    if len(s) > 1:
                        if s[-2] not in {'+', '-', '*'}:
                            search(s, i + 1)
                else:
                    search(s, i + 1)
                search(s + '+', i + 1)
                search(s + '-', i + 1)
                search(s + '*', i + 1)
            else:
                judge(s)

        search('', 0)
        return out



data = Solution()
num = "105"
target = 5
print(data.addOperators(num, target))
num = "00"
target = 0
print(data.addOperators(num, target))